// 摘自https://zhuanlan.zhihu.com/p/1973166704931657240
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e5 + 5; // 定义最大数值范围
ll a[N];               // 存储每个位置的数值

// 计算lowbit：获取一个数的最低位的1所代表的值

// 树状数组（BIT）数据结构
struct BIT {
  int size;        // 树状数组的大小
  vector<ll> tree; // 树状数组的存储结构
  inline int lowbit(int x) { return x & -x; }

  // 构造函数：初始化大小为n的树状数组
  BIT(int n) : size(n), tree(n + 1, 0) {}

  // 单点修改：在位置pos增加val
  void modify(int pos, ll val) {
    if (pos <= 0)
      return; // 边界检查
    // 树状数组的标准更新操作：从pos开始，每次加上lowbit(i)
    for (int i = pos; i <= size; i += lowbit(i)) {
      tree[i] += val;
    }
  }

  // 前缀和查询：查询[1, pos]的和
  ll query(int pos) {
    if (pos <= 0)
      return 0; // 边界检查
    ll res = 0;
    // 树状数组的标准查询操作：从pos开始，每次减去lowbit(i)
    for (int i = pos; i > 0; i -= lowbit(i)) {
      res += tree[i];
    }
    return res;
  }

  // 区间和查询：查询[l, r]的和
  ll query(int l, int r) {
    if (l > r)
      return 0; // 无效区间
    // 边界处理
    if (l <= 0)
      l = 1;
    if (r > size)
      r = size;
    // 区间和 = 前缀和[r] - 前缀和[l-1]
    return query(r) - query(l - 1);
  }
};

// 核心思路：将数值分为三个区间计算贡献
// [0, l): 贡献为 l * 该区间数字个数
// [l, r]: 贡献为 该区间数字之和
// (r, ∞): 贡献为 r * 该区间数字个数

int main() {
  int n, q; // n: 数字个数, q: 查询次数
  cin >> n >> q;

  // 创建两个树状数组：
  BIT bt1(N); // bt1: 维护数字出现的次数（计数）
  BIT bt2(N); // bt2: 维护数字的总和

  // 初始化：读入所有数字并更新树状数组
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    bt1.modify(a[i], 1);    // 在a[i]位置计数+1
    bt2.modify(a[i], a[i]); // 在a[i]位置总和+a[i]
  }

  // 处理每个查询
  while (q--) {
    ll op, x, y, l, r;
    cin >> op;

    if (op == 1) {
      // 修改操作：将第x个位置的数值改为y
      cin >> x >> y;

      // 先删除原来的数值
      bt1.modify(a[x], -1);    // 在原数值位置计数-1
      bt2.modify(a[x], -a[x]); // 在原数值位置总和-原数值

      // 更新数值
      a[x] = y;

      // 添加新的数值
      bt1.modify(a[x], 1);    // 在新数值位置计数+1
      bt2.modify(a[x], a[x]); // 在新数值位置总和+新数值

    } else {
      // 查询操作：计算三个区间的总贡献
      cin >> l >> r;

      // 特殊情况：当l > r时，所有数字的贡献都是l
      if (l > r) {
        cout << l * n << endl;
        continue;
      }

      ll ans = 0;

      // 第一部分：[0, l) 区间的贡献
      // 该区间内每个数字的贡献都是l
      ans += bt1.query(l - 1) * l; // 个数 * l

      // 第二部分：[l, r] 区间的贡献
      // 该区间内每个数字的贡献就是数字本身
      ans += bt2.query(l, r); // 直接求和

      // 第三部分：(r, ∞) 区间的贡献
      // 该区间内每个数字的贡献都是r
      ans += bt1.query(r + 1, N - 1) * r; // 个数 * r

      cout << ans << endl;
    }
  }

  return 0;
}